Methods for compressing data to increase the amount of data which may be transmitted through the existing bandwidth of a conduit are well known. Such methods are used by a compressor or encoder to determine functions which represent data being input to a system. The functions require less information to describe than the data being represented so less data is transmitted. Thus, the transmission of the elements describing the function which represents the original data set may be done more quickly or with less processing than the original data set itself. Once the functions have been transmitted, a decompressor or decoder at the receiving site may use the function to regenerate the original data set at the receiving site.
One well known data compression method is the fractal transform method. This method is the subject of a number of patents including U.S. Pat. Nos. 5,065,447 and 5,384,867 to Barnsley, et al. The fractal transform technique is based upon the theory that data, especially image data, is comprised of redundant information. As a result, many portions of the data contained within a data set may be expressed in terms of other data within the set. By identifying those portions which are common to many subsets of the data in the original set and determining the functions which map the subsets to the redundant data, an encoder may then use the subset identifiers and mapping functions to describe the original data set. These subset identifiers and mapping functions may be transmitted to a decoder which implements a deterministic or random iterative method to regenerate the original data set. In the fractal transform method, the data subsets are typically called domains, while the redundant information is derived from ranges. The steps of dividing a data set into domains and ranges so the mapping functions which best describe the original data set may be determined are set forth in the patents identified above and are hereby expressly incorporated herein by reference.
The use of fractal transform techniques to compress data has proliferated, especially in the image field. This proliferation has led to a number of variations in compressor and decompressor designs. For example, some fractal transform systems use affine map transformations to represent data sets while other systems may use polynomial functions or the like. Even within systems which use affine map transformations, each system may vary in the coefficient matrices which are used to evaluate the correspondence of a domain to a range. In fact, compressors may vary many different parameters to compress data such as the sizes and shapes of the ranges and domains used and the methods for shrinking the ranges to form orientation blocks. As a result, the identifiers of the domains and ranges and the mapping functions generated to represent data sets may vary widely from one compressor to another.
Known methods for transmitting domain and range identifiers with mapping functions are tailored to correspond to compression and decompression methods implemented for particular applications. That is, the transmission methods are adapted to the particular parameters implemented in a compressor. These transmission methods are not readily adaptable to other applications or compressor/decompressor designs. Since the transmission methods are limited in the data delivered to a decompressor, the decompressor design is usually limited to performing the inverse process of a compressor for a particular application. While this limited decompressor design and tailoring of the data transmission method may reduce the processing and time needed for transmission and decompression of the fractal transform data, it may not support variations of fractal transform parameters used for different applications or communication with decompressors other than those designed for a particular application. What is needed is a data transmission method that supports variations of fractal transform parameters so a variety of decompressors may use the data to decompress images.
Most compressors are designed to use a group of coefficient matrices which are computationally efficient and which generally provide good correspondence between domains and ranges. As a result, some shorthand notation scheme may be used by a transmission method to identify these matrices. However, some original data sets contain domains which are difficult to match to a range. For example, in an area of an image where there is a great degree of detail, matrices having computationally complex coefficients may be required to map the domain to a range. Identification of such a matrix in current transmission methods is done in a way which requires either special processing to detect and decode the matrix at the decompressor or the inclusion of the coefficient matrix for each domain despite the frequent use of one or more matrices. What is needed is a fractal transform data transmission method which provides coefficient matrices used for only one domain without sacrificing the ability to use a shorthand scheme to identify more frequently used matrices.
One of the advantages of fractal transform methods is its independent image resolution property. This property is apparent in the magnification of an image or in displaying an image on a device having a display space with a different size and resolution than the image input device. In pixel oriented schemes, the magnification level may get to a level where the information in a pixel is reproduced many times to cover an expanded area in a magnified view. Such reproduction generates "block" structure rather than detail. Likewise, pixel oriented systems do not convert image information well from one screen of a first height and width to a screen having a second height and width. Both of these limitations arise because such systems must determine how to move the pixels and perhaps generate other pixels to conform the informational content generated by the input device or the area to be magnified to the display elements of the output device or magnification space. Fractal imaging techniques generate mapping functions for one area of an image to another so the location of the domains and ranges defining those areas may be described with a continuous measurement unit such as an inch rather than a discrete unit such as a pixel. As a result, the domains and ranges may be shifted, expanded and contracted more easily than pixel oriented systems where the number and height/width ratio of the pixels may not be compatible with a second pixel system. In fractal transform systems, the mapping functions are able to generate the informational content for the modified areas. As a result, fractal transformed image data may be used to provide magnification detail as some portion of an image is expanded or to provide an image on an output device with a different pixel resolution and size than the input device. Current transmission schemes for fractal transform data are specifically drawn to an application and usually correspond to the input/output limitations expected for the applications. Consequently, they typically define the pixel locations for domains and ranges with reference to the device characteristics for the application. As a result, decompressors are limited by the resolution parameters of the input/output devices. What is needed is a method of data transmission that provides image information in a resolution independent manner.
Fractal images are generated by a variety of devices which represent data very differently. For example, image data may be generated by facsimile transmission machines which typically generate data using grayscale information or an image scanner which may generate colorized images in any of a number of color space systems. In some compressors, the color space of an input image may be converted to another color space before it is compressed. For example, a compressor may convert an image from a red-green-blue (RGB) color space to a luminance/chrominance (YUV) color space to take advantage of some computational advantages of that color space. To properly decompress the data to regenerate the image, the decompressor needs to be able to identify the color components comprising the image as compressed and convert them to the original color space for display. As discussed above, compressor/decompressor combinations are typically developed for a particular application so the compressor/decompressor and the data transmission between them only support the color system or systems used in the application. What is needed is a fractal transform data transmission method which identifies the parameters for converting between any of a number of known color systems regardless of application.
Another problem arises because some compressors distort the color space during compression and may include processing to correct the distortion. Such processing may adjust the image data before it is compressed or may modify the color of the compressed data before transmission. Current transmission methods only provide information about the specific way the data is processed to compensate for the distortion. Such a limited transmission method requires that the decompressor be designed to identify the compensation factors and implement the distortion correction on the image or compressed data. As a result, there is no data transmission method which provides a general system for providing information for conversions between most known color systems which incorporate the distortion correction data. What is needed is a fractal transform data transmission method which incorporates distortion compensation information along with color space conversion information.
What is needed is a fractal transform data transmission method which provides fractal transform information in a resolution independent manner with color space information so that a compressor and decompressor need not be designed to implement the compression and decompression processes for a particular application.